#define _CRT_SECURE_NO_WARNINGS 1
#include<stack>
using namespace std;
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };
 
class Solution {
public:
    bool FindNode(TreeNode* root, int find, stack<TreeNode*>& st)
    {
        if (root == nullptr)
        {
            return false;
        }
        st.push(root);
        if (root->val == find)
        {
            return true;
        }
        bool left = FindNode(root->left, find, st);
        bool right = FindNode(root->right, find, st);
        if (!left && !right)
        {
            st.pop();
        }
        return left || right;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        stack<TreeNode*> st1;
        FindNode(root, p->val, st1);
        stack<TreeNode*> st2;
        FindNode(root, q->val, st2);
        while (st1.top() != st2.top())
        {
            if (st1.size() > st2.size())
            {
                st1.pop();
            }
            else
            {
                st2.pop();
            }
        }
        return st1.top();
    }
};